package org.codetranslators.compiler.liveness;

import java.util.Vector;
import java.util.HashMap;
import java.util.Iterator;
import java.util.BitSet;

import org.codetranslators.common.Temp;
import org.codetranslators.compiler.intermrep.AssemblyInstruction;

public class ControlFlowGraph extends Graph
{
	private Vector instructionsList; 
	private HashMap keyVsNodes;
	private HashMap nodesVsUseDefs;
	private Vector tempsSet;
	
	private int numNodes;
	private int numTemps;
	
	public ControlFlowGraph(Vector instList)
	{
		super(instList.size());
		instructionsList = instList;
		keyVsNodes = new HashMap();
		nodesVsUseDefs = new HashMap();
		tempsSet = new Vector();
		numNodes = instructionsList.size();
		
		createFlowGraph();  // Create the flow graph
	}

	public Vector getInstructionsList() 
	{
		return instructionsList;
	}
	
	private void createFlowGraph()
	{
		for(int i = 0; i < numNodes; i++)
		{
			AssemblyInstruction instr = (AssemblyInstruction) instructionsList.elementAt(i);
			Vector jumpsList = instr.getJumps();
			
			Node newInsNode = newNode(i, instr);
			
			if(jumpsList != null)
			{
				// This must be either a jump or a cjump
				int numJumps = jumpsList.size();
				for(int j = 0; j < numJumps; j++)
				{
					String jmpStr = (String) jumpsList.elementAt(j);
					Node nextNode = getNodeAfterLabel(jmpStr);
					addEdge(newInsNode, nextNode);
				}
			}
			else
			{
				// This must be either a label or an operation
				if(i != numNodes -1)
				{
					// Not the last instruction; get the next instruction and add and edge
					Node nextNode = getNextInstr(i);
					if(nextNode != null) addEdge(newInsNode, nextNode);
				}
			}
		}
		
		numTemps = tempsSet.size();
	}
	
	/* Returns the next non-label instruction and creates it if required
	 * 
	 */
	private Node getNextInstr(int n)
	{
		Node nextNode = null;
		
		int numIns = instructionsList.size();
		for(int i = n+1; i < numIns; i++)
		{
			AssemblyInstruction instr = (AssemblyInstruction) instructionsList.elementAt(i);
			if(instr.getLabelStr() == null)
			{
				// This is a non-label instruction; create a new node for this and return
				nextNode = newNode(i, instr);
				break;
			}
		}
		return nextNode;
	}
	
	private Node newNode(int i, AssemblyInstruction instr)
	{
		Node node = (Node)keyVsNodes.get("" + i);
		if(node != null) return node;
		
		// This node does not exist already; create a new one
		node = super.newNode("" + i);
		
		//associate the use and defs
		Vector srcList = instr.getSrcList();
		Vector destList = instr.getDestList();
		addToTempList(srcList);
		addToTempList(destList);
		CfgProperties useDef = new CfgProperties(srcList, destList, instr.isMove());
		nodesVsUseDefs.put(node, useDef);
		
		// put the new entry by marking it as created
		keyVsNodes.put(""+i, node);
		return node;
	}
	
	private Node getNodeAfterLabel(String jmpStr)
	{
		int numIns = instructionsList.size();
		Node nodeAfterLabel = null;
		for(int i = 0; i < numIns; i++)
		{
			AssemblyInstruction instr = (AssemblyInstruction) instructionsList.elementAt(i);
			String lblFound = instr.getLabelStr();   // can be null
			if(jmpStr.equals(lblFound))
			{
				if(i == numIns -1)
				{
					// The last instruction; return it
					nodeAfterLabel =  newNode(i, instr);
				}
				else
				{
					instr = (AssemblyInstruction) instructionsList.elementAt(i +1);
					nodeAfterLabel =  newNode(i + 1, instr);
				}
				break;
			}
		}
		return nodeAfterLabel;
	}
	
	public void show(java.io.PrintStream out) 
	{
		int ndCount = getNodeCount();
		Vector allNodes = nodes();
		for (int i = 0; i < ndCount; i++)
		{
			Node n = (Node) allNodes.elementAt(i);
			out.print("" + i);
			out.print(": ");
			  
			CfgProperties useDef = (CfgProperties) nodesVsUseDefs.get(n);
			Vector defList = useDef.getDefList();
			if(defList != null)
			{
				int numDefs = defList.size();
				for(int j = 0; j < numDefs; j++) 
				{
					Temp dfTemp = (Temp) defList.elementAt(j);
					out.print(dfTemp.toString());
					out.print(" ");
				}
			}
			else out.print("None ");
			
			out.print(useDef.isMove() ? "<= " : "<- ");
			
			Vector useList = useDef.getUseList();
			if(useList != null)
			{
				int numUses = useList.size();
				for(int k = 0; k < numUses; k++) 
				{
					Temp usTemp = (Temp) useList.elementAt(k);
					out.print(usTemp.toString());
				    out.print(" ");
				}
			}
			else out.print("None ");
			
			out.print("; goto ");
			
			Vector succs = n.getSuccessors();
			if(succs != null)
			{
				int numSuccs = succs.size();
				for(int j = 0; j < numSuccs; j++) 
				{
					Node succ = (Node) succs.elementAt(j);
				    out.print(succ.getId());
				    out.print(" ");
				}
			}
			out.println();
		}
	}
	
	private void addToTempList(Vector list)
	{
		if(list == null) return;
		int numTemps = list.size();
		for(int i = 0; i < numTemps; i++)
		{
			Temp tmp = (Temp)list.elementAt(i);
			if(!tempsSet.contains(tmp))
				tempsSet.addElement(tmp);
		}
	}
	
	/*
	public int[] getTempIndex(Vector list)
	{
		for(int i = 0; i < list.size(); i++)
		{
			Temp temp = (Temp) list.elementAt(i);
			int index = tempsSet.indexOf(temp);
		}
	}*/
	
	public int getNumTemps()
	{
		return tempsSet.size();
	}
	
	public void showTemps()
	{
		Iterator iter = tempsSet.iterator();
		while(iter.hasNext())
		{
			Temp tmp = (Temp) iter.next();
			System.out.print(tmp.toString() + " ");
		}
		System.out.println(" ");
	}
	
	public BitSet getUsesBitVector(Node node)
	{
		return getBitVector(node, true);
	}
	
	public BitSet getDefsBitVector(Node node)
	{
		return getBitVector(node, false);
	}
	
	private BitSet getBitVector(Node node, boolean forUses)
	{
		BitSet bitSet = null;
		
		CfgProperties props = (CfgProperties) nodesVsUseDefs.get(node);
		if(forUses)
			bitSet = props.getUsesBitVector();
		else
			bitSet = props.getDefsBitVector();
		
		if(bitSet != null) return bitSet;
		
		// Not been calculated so far; calculate it
		Vector list = null;
		if(forUses)
			list = props.getUseList();
		else
			list = props.getDefList();
		
		bitSet = new BitSet(numTemps);
		bitSet.clear();
		
		if(list == null) return bitSet;  // No uses or defs for this node
		
		for(int i = 0; i < list.size(); i++)
		{
			Temp temp = (Temp) list.elementAt(i);
			int index = tempsSet.indexOf(temp);
			bitSet.set(index);
		}
		
		if(forUses)
			props.setUsesBitVector(bitSet);
		else
			props.setDefsBitVector(bitSet);
		
		return bitSet;
	}
	
	public Temp getTemp(int index)
	{
		return (Temp) tempsSet.elementAt(index);
	}
	
	public Vector getTempsSet()
	{
		return tempsSet;
	}
	
	public CfgProperties getCfgProperties(Node node)
	{
		return (CfgProperties) nodesVsUseDefs.get(node); 
	}
}
